/**
 * 二分查找
 * @param {[number, number][]} arr
 * @param {[number, number]} target
 * @param {0 | 1} lOrR 0: 查找leftIndex,找出最大一个比left小的下标. 1: 查找rightIndex,找出最小一个比right大的下标
 * @returns {number}
 */
function bisect(arr, target, lOrR = 0) {
  let left = 0
  let right = arr.length - 1
  let ans = -1
  while (left <= right) {
    const mid = (left + right) >> 1
    if (target[lOrR] === arr[mid][lOrR]) return mid
    if (target[lOrR] > arr[mid][lOrR]) {
      if (lOrR === 0) ans = mid
      left = mid + 1
    } else {
      if (lOrR === 1) ans = mid
      right = mid - 1
    }
  }
  return ans
}

export var RangeModule = function () {
  this.ranges = []
}

/**
 * @param {number} left
 * @param {number} right
 * @return {void}
 */
RangeModule.prototype.addRange = function (left, right) {
  // console.log('add', left, right, this.ranges)
  const ranges = this.ranges
  const target = [left, right]
  if (ranges.length === 0) {
    this.ranges.push(target)
    return
  }
  // 处理在最右情况
  if (left > ranges[ranges.length - 1][1]) {
    this.ranges.push(target)
    return
  }
  if (left === ranges[ranges.length - 1][1]) {
    this.ranges[ranges.length - 1][1] = right
    return
  }
  // 在最左
  if (right < ranges[0][0]) {
    this.ranges.unshift(target)
    return
  }
  if (right === ranges[0][0]) {
    this.ranges[0][0] = left
    return
  }

  let rightIdx = bisect(ranges, target, 1)
  let leftIdx = bisect(ranges, target, 0)
  // 1, left 和 right 的范围cover所有的范围
  if (leftIdx === -1 && rightIdx === -1) {
    this.ranges = [[left, right]]
    return
  }

  // 2 当leftIdx === rightIdx时，说明刚好落在某一个范围内，不用处理
  if (leftIdx === rightIdx) return

  // 3余下的是 left < rightIdx
  // console.log(`left: ${left} right: ${right} leftIdx: ${leftIdx} rightIdx: ${rightIdx}`)
  const deleteStartIdx = leftIdx === -1 ? 0 : left <= ranges[leftIdx][1] ? leftIdx : leftIdx + 1
  const deleteEndIdx =
    rightIdx === -1
      ? ranges.length - 1
      : right >= ranges[rightIdx][0]
      ? rightIdx
      : rightIdx - 1 < 0
      ? 0
      : rightIdx - 1
  // console.log('dsi',ranges, deleteStartIdx,deleteEndIdx)
  const newLeft = Math.min(ranges[deleteStartIdx][0], left)
  const newRight = Math.max(ranges[deleteEndIdx][1], right)
  this.ranges.splice(deleteStartIdx, deleteEndIdx - deleteStartIdx + 1, [newLeft, newRight])

  return
}

/**
 * @param {number} left
 * @param {number} right
 * @return {boolean}
 */
RangeModule.prototype.queryRange = function (left, right) {
  // console.log('query', left, right, this.ranges)
  if (this.ranges.length === 0) return false
  if (right > this.ranges[this.ranges.length - 1][1]) return false
  if (left < this.ranges[0][0]) return false

  let [l, r] = [0, this.ranges.length - 1]
  while (l <= r) {
    const mid = (l + r) >> 1
    if (left >= this.ranges[mid][0] && right <= this.ranges[mid][1]) return true
    if (left > this.ranges[mid][1]) l = mid + 1
    else r = mid - 1
  }
  return false
}

/**
 * @param {number} left
 * @param {number} right
 * @return {void}
 */
RangeModule.prototype.removeRange = function (left, right) {
  // console.log('remove', left, right, this.ranges)
  const ranges = this.ranges
  if (ranges.length === 0) return
  if (left >= ranges[ranges.length - 1][1]) return
  if (right <= ranges[0][0]) return

  const target = [left, right]
  let rightIdx = bisect(ranges, target, 1)
  let leftIdx = bisect(ranges, target, 0)

  // 1, left 和 right 的范围cover所有的范围
  if (leftIdx === -1 && rightIdx === -1) {
    this.ranges = []
    return
  }

  // 2 当leftIdx === rightIdx时，须要把leftIdx的范围拆成成两个范围
  if (leftIdx === rightIdx) {
    const leftRange = ranges[leftIdx][0] === left ? null : [ranges[leftIdx][0], left]
    const rightRange = ranges[leftIdx][1] === right ? null : [right, ranges[leftIdx][1]]
    const items = []
    if (leftRange) items.push(leftRange)
    if (rightRange) items.push(rightRange)
    this.ranges.splice(leftIdx, 1, ...items)
    return
  }

  // 3余下的是 left < rightIdx
  const deleteStartIdx = leftIdx + 1
  const deleteEndIdx = rightIdx === -1 ? ranges.length - 1 : rightIdx - 1

  if (leftIdx !== -1 && left < ranges[leftIdx][1]) this.ranges[leftIdx][1] = left
  if (rightIdx !== -1 && right > ranges[rightIdx][0]) this.ranges[rightIdx][0] = right
  if (deleteStartIdx <= deleteEndIdx)
    this.ranges.splice(deleteStartIdx, deleteEndIdx - deleteStartIdx + 1)
  return
}

/**
 * Your RangeModule object will be instantiated and called as such:
 * var obj = new RangeModule()
 * obj.addRange(left,right)
 * var param_2 = obj.queryRange(left,right)
 * obj.removeRange(left,right)
 */
